#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <time.h>
#include <sys/time.h>
#include <upc.h>

//
// auxiliary functions
//
inline int max( int a, int b ) { return a > b ? a : b; }
inline int min( int a, int b ) { return a < b ? a : b; }
double read_timer( )
{
    static int initialized = 0;
    static struct timeval start;
    struct timeval end;
    if( !initialized )
    {
        gettimeofday( &start, NULL );
        initialized = 1;
    }
    gettimeofday( &end, NULL );
    return (end.tv_sec - start.tv_sec) + 1.0e-6 * (end.tv_usec - start.tv_usec);
}


// Spin until an item's value is not -1
int get_item(shared int *alias_row, int c, int index)
{
  int ret = -1;
  while((ret = alias_row[index]) == -1) { }
  return ret;
}

// Builds the table
int build_table_row( int nitems, int cap, shared int *T, shared int *alias, shared int *w, shared int *v )
{
    // Parallelize rows
    upc_forall(int c = 1; c <= cap; c++; &T[c*nitems] ) {
      shared int *weights = &w[MYTHREAD*nitems];
      shared int *values = &v[MYTHREAD*nitems];
      // Get our row of the T table
      shared int *row = &T[c*nitems];
      shared int *alias_row = &alias[c*nitems];

      // Loop over items in row
      for (int i = 0; i < nitems; i++) {
        
        if (c < weights[i]) // Item i won't fit
          row[i] = (i > 0) ? row[i - 1] : 0;
        else if (c == weights[i])
          row[i] = (i > 0) ? max(row[i - 1], values[i]) : values[i];
        else // Item i fits
          row[i] = (i > 0) ? max(row[i - 1], values[i]+get_item(alias_row, c, i)) : values[i];
       
        // Copy row for use by other threads (put in alias table)
        if (i+1 < nitems ) { 
          int insert_c = c + weights[i+1];
          if (insert_c <= cap) { 
            alias[insert_c*nitems + i+1] = row[i];
          }
        }
      }
    }
  
    upc_barrier;

    return T[nitems*cap + nitems - 1];
}

void backtrack( int nitems, int cap, shared int *T, shared int *w, shared int *u )
{
    if( MYTHREAD != 0 )
        return;
  
  int i = nitems*(cap+1) - 1;
  for (int col = nitems-1; col > 0; col--) {
    u[col] = T[i] != T[i-1];
    i -= 1 + nitems*(u[col] ? w[col] : 0);
  }
  u[0] = T[i] != 0;
}

//
//  serial solver to check correctness
//
int solve_serial( int nitems, int cap, shared int *w, shared int *v )
{
    int i, j, best, *allocated, *T, wj, vj;
    
    //alloc local resources
    T = allocated = malloc( nitems*(cap+1)*sizeof(int) );
    if( !allocated )
    {
        fprintf( stderr, "Failed to allocate memory" );
        upc_global_exit( -1 );
    }
    
    //build_table locally
    wj = w[0];
    vj = v[0];
    for( i = 0;  i <  wj;  i++ ) T[i] = 0;
    for( i = wj; i <= cap; i++ ) T[i] = vj;
    for( j = 1; j < nitems; j++ ) 
    {
        wj = w[j];
        vj = v[j];
        for( i = 0;  i <  wj;  i++ ) T[i+cap+1] = T[i];
        for( i = wj; i <= cap; i++ ) T[i+cap+1] = max( T[i], T[i-wj]+vj );
        T += cap+1;
    }
    best = T[cap];
    
    //free resources
    free( allocated );
    
    return best;
}

#define CAP 999

shared int * shared test;

int main( int argc, char** argv )
{
    int i, j, best_value, best_value_serial, total_weight, nused, total_value;
    double seconds;
    shared int *weight;
    shared int *value;
    shared int *used;
    shared int *total, *alias;
 
    //these constants have little effect on runtime
    int max_value  = 1000;
    int max_weight = 1000;
    
    //these set the problem size
    int capacity   = 999;
    int nitems     = 5000;

    //srand48( (unsigned int)time(NULL) + MYTHREAD );
    srand48(0);

    // Garunteed not to have any rows wrap over. Each thread has contiguous set of rows.
    int rows_per_thread = ceil((double) (capacity+1) / THREADS);
    //shared int * shared_data = (shared int *) upc_all_alloc(THREADS, rows_per_thread * nitems * sizeof(int));
    int * local_rows = (int *) malloc(rows_per_thread * nitems * sizeof(int));
    int * row_thread = (int *) malloc((capacity+1) * sizeof(int));

    if (MYTHREAD == 0) {
    shared int * foo =  upc_global_alloc(2, 4*sizeof(int)); 
    for (int i = 0; i < 8; i++) {
      printf("foo[%d] is on thread %d\n", i, upc_threadof(foo+i));
    }
    }
/*
    for (int i = 0; i < THREADS; i++) {
      int start = i*rows_per_thread;
      int stop = min((i+1)*rows_per_thread, capacity+1) - 1;
      for (int j = start; j <= stop; j++) {
        if (MYTHREAD == 0)
        if (upc_threadof(&shared_data[j*nitems]) != i) printf("ThreadOf[%d] = %d, we think %d\n", j*nitems, upc_threadof(&shared_data[j]), i);
        row_thread[j] = i;
      }

      if (MYTHREAD == 0) {
        printf("Thread %d: %d rows [%d to %d]\n", i, stop-start+1, start, stop);
      }
    }
*/
    return 0;
/*
  Error cannot allocate shared pointer.
  UPC does not support shared auto variables.

    // Allocate dynamic-programming table. Manually assign rows to threads.
    shared int * * shared shared_data = (shared int *) upc_all_alloc(1, THREADS * sizeof(int));
    int *row_thread = (int *) malloc((capacity+1)*sizeof(int));

    double rows_per_thread = (double) (capacity+1) / THREADS;
    double sum = 0; 
    for (int i = 0; i < THREADS; i++) {
      int start = floor(sum) + 1;
      sum += rows_per_thread;
      int stop = (i == THREADS - 1) ? capacity + 1 : floor(sum);


      for (int j = start; j <= stop; j++) row_thread[j] = i;
      if (i == MYTHREAD) {
        printf("Thread %d alloc %d rows (%d to %d)\n", MYTHREAD, stop-start+1, start, stop);
        shared_data[i] = (int) upc_alloc(stop-start+1 * sizeof(int));
      }
    }

    upc_barrier

    printf("Thread %d sees: ", MYTHREAD);
    for (int i = 0; i < THREADS; i++) {
      printf("%x\t", (unsigned int) shared_data[i]);
    }
    printf("\n");
*/
    return 0;

    // Replicate this data once per THREAD
    weight = (shared int *) upc_all_alloc( THREADS, nitems * sizeof(int) );
    value  = (shared int *) upc_all_alloc( THREADS, nitems * sizeof(int) );
    used   = (shared int *) upc_all_alloc( THREADS, nitems * sizeof(int) );
    // Block by rows
    //int rows_per_thread = ceil((double)(capacity+1) / THREADS);
    total  = (shared int *) upc_all_alloc( THREADS, rows_per_thread * nitems * sizeof(int) );
    alias  = (shared int *) upc_all_alloc( THREADS, rows_per_thread * nitems * sizeof(int) );
    //total  = (shared int *) upc_all_alloc( capacity+1, nitems * sizeof(int) );
    //alias  = (shared int *) upc_all_alloc( capacity+1, nitems * sizeof(int) );
    
    if( !weight || !value || !total || !alias || !used ) {
        fprintf( stderr, "Failed to allocate memory" );
        upc_global_exit( -1 );
    }

    // init
    if (MYTHREAD == 0) {
      for ( i = 0; i < nitems*(capacity+1); i++) {
        alias[i] = -1;
      }

      max_weight = min( max_weight, capacity );   //don't generate items that don't fit into bag
      for( i = 0; i < nitems; i++) {
        int w = 1 + (lrand48()%max_weight);
        int v = 1 + (lrand48()%max_value);
        for ( j = 0; j < THREADS; j++) {
          weight[j*nitems + i] = w; 
          value[j*nitems + i]  = v;
        }
      } 
    }
 
    upc_barrier;

    // time the solution
    seconds = read_timer( );
    
    best_value = build_table_row( nitems, capacity, total, alias, weight, value );
    backtrack( nitems, capacity, total, weight, used );
    
    seconds = read_timer( ) - seconds;
    
    // check the result
    if( MYTHREAD == 0 )
    {
        printf( "%d items, capacity: %d, time: %g\n", nitems, capacity, seconds );
        
        best_value_serial = solve_serial( nitems, capacity, weight, value );
        
        total_weight = nused = total_value = 0;
        for( i = 0; i < nitems; i++ )
            if( used[i] )
            {
                nused++;
                total_weight += weight[i];
                total_value += value[i];
            }
        
        printf( "%d items used, value %d, weight %d\n", nused, total_value, total_weight );
        
        if( best_value != best_value_serial || best_value != total_value || total_weight > capacity )
            printf( "WRONG SOLUTION\n" );
        
        //release resources
        upc_free( weight );
        upc_free( value );
        upc_free( total );
        upc_free( used );
    }
    
    return 0;
}
